package com.shm.leetcode;

/**
 * 132. 分割回文串 II
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
 *
 * 返回符合要求的 最少分割次数 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aab"
 * 输出：1
 * 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
 * 示例 2：
 *
 * 输入：s = "a"
 * 输出：0
 * 示例 3：
 *
 * 输入：s = "ab"
 * 输出：1
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 2000
 * s 仅由小写英文字母组成
 * @author SHM
 */
public class MinCut {
    /**
     * 动态规划解法
     * 如果昨天的 「每日一题」 你有使用到 DP 进行预处理的话。
     *
     * 这道题就很简单了，就是一道常规的动态规划题目。
     *
     * 递推「最小分割次数」思路
     * 我们定义 f[i] 为以下标为 i 的字符作为结尾的最小分割次数，那么最终答案为 f[n - 1]。
     *
     * 不失一般性的考虑第 j 字符的分割方案：
     *
     * 从起点字符到第 j 个字符能形成回文串，那么最小分割次数为 0。此时有 f[j] = 0
     * 从起点字符到第 j 个字符不能形成回文串：
     * 该字符独立消耗一次分割次数。此时有 f[j] = f[j - 1] + 1
     * 该字符不独立消耗一次分割次数，而是与前面的某个位置 i 形成回文串，[i, j] 作为整体消耗一次分割次数。此时有 f[j] = f[i - 1] + 1
     * 在 2.2 中满足回文要求的位置 i 可能有很多，我们在所有方案中取一个 min 即可。
     *
     * 快速判断「任意一段子串是否回文」思路
     * 剩下的问题是，我们如何快速判断连续一段 [i, j] 是否为回文串，做法和昨天的 「每日一题」 一模一样。
     *
     * PS. 昨天的题目，数据范围只有 16，因此我们可以不使用 DP 进行预处理，而是使用双指针来判断是否回文也能过。但是该题数据范围为 2000（数量级为 10^310
     * 3
     *  ），使用朴素做法判断是否回文的话，复杂度会去到 O(n^3)O(n
     * 3
     *  )（计算量为 10^910
     * 9
     *  ），必然超时。
     *
     * 因此我们不可能每次都使用双指针去线性扫描一遍 [i, j] 判断是否回文。
     *
     * 一个直观的做法是，我们先预处理除所有的 f[i][j]，f[i][j] 代表 [i, j] 这一段是否为回文串。
     *
     * 预处理 f[i][j] 的过程可以用递推去做。
     *
     * 要想 f[i][j] == true ，必须满足以下两个条件：
     *
     * f[i + 1][j - 1] == true
     * s[i] == s[j]
     * 由于状态 f[i][j] 依赖于状态 f[i + 1][j - 1]，因此需要我们左端点 i 是从大到小进行遍历；而右端点 j 是从小到大进行遍历。
     *
     * 我们的遍历过程可以整理为：右端点 j 一直往右移动（从小到大），在 j 固定情况下，左端点 i 在 j 在左边开始，一直往左移动（从大到小）
     *
     * 时间复杂度：O(n^2)O(n
     * 2
     *  )
     * 空间复杂度：O(n^2)O(n
     * 2
     *  )
     * 关于「如何确定 DP 状态定义」的分享
     * 有同学会对「如何确定 DP 的状态定义」有疑问，觉得自己总是定不下 DP 的状态定义。
     *
     * 首先，十分正常，不用担心。
     *
     * DP 的状态定义，基本上是考经验的（猜的），猜对了 DP 的状态定义，基本上「状态转移方程」就是呼之欲出。
     *
     * 虽然大多数情况都是猜的，但也不是毫无规律，相当一部分是定义是与「结尾」和「答案」有所关联的。
     *
     * 例如本题定义 f[i] 为以下标为 i 的字符作为结尾（结尾）的最小分割次数（答案）。
     *
     * 因此对于那些你没见过的 DP 模型题，可以从这两方面去「猜」。
     *
     *
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/xiang-jie-liang-bian-dong-tai-gui-hua-ji-s5xr/
     * @param s
     * @return
     */
    public int minCut(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        // 预处理出 st，st[i][j] 表示区间 [i,j] 是否为回文串
        boolean[][] st = new boolean[n][n];
        for(int j=0;j<n;j++){
            for(int i=j;i>=0;i--){
                // 当 [i, j] 只有一个字符时，必然是回文串
                if(i==j){
                    st[i][j]=true;
                    // 当 [i, j] 长度为 2 时，满足 cs[i] == cs[j] 即回文串
                }else if(j-i+1==2){
                    st[i][j] = cs[i]==cs[j];
                }else{
                    // 当 [i, j] 长度大于 2 时，满足 (cs[i] == cs[j] && f[i + 1][j - 1]) 即回文串
                    st[i][j] = cs[i]==cs[j]&&st[i+1][j-1];
                }
            }
        }
        // f(i) 代表考虑下标为 i 的字符为结尾的最小分割次数
        int[] f = new int[n];
        for(int j=1;j<n;j++){
            // 如果 [0,j] 这一段直接构成回文，则无须分割
            if(st[0][j]){
                f[j]=0;
            }else{
                // 如果无法直接构成回文
                // 那么对于第 j 个字符，有使用分割次数，或者不使用分割次数两种选择
                f[j]=f[j-1]+1;
                // 第 j 个字符本身不独立使用分割次数
                // 代表要与前面的某个位置 i 形成区间 [i,j]，使得 [i, j] 形成回文，[i, j] 整体消耗一次分割次数
                for(int i=1;i<j;i++){
                    if(st[i][j]) {
                        f[j] = Math.min(f[j], f[i-1] + 1);
                    }
                }
            }
        }
        return f[n-1];
    }
}
